package com.lwl.leetcode;

import org.junit.Test;

/**
 * @author lwl
 * @Description TODO
 * @date 2023/8/1 10:25
 */
public class Code41FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 出现以下情况，最大的正整数都不可能超过right，而且需要收缩right
            // 1. 当前数大于right
            // 2. 当前数小于left(说明当前数在之前已经重复)
            // 3. 以当前数作下标对应的元素相等(说明后面的这个数会重复)
            // 3. 当前数小于零
            if (nums[left] > right || nums[left] <= left || nums[left] == nums[nums[left]] || nums[left] <= 0) {
                swap(nums, left, right--);
                continue;
            }
            if (nums[left] == left + 1) {
                left++;
            } else {
                swap(nums, nums[left], left);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i] - 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    private void swap(int[] array, int i, int j) {
        if (i == j) {
            return;
        }
        array[i] += array[j];
        array[j] = array[i] - array[j];
        array[i] = array[i] - array[j];
    }

    @Test
    public void test() {
        System.out.println(firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(firstMissingPositive(new int[]{2, 2, 2, 2, 2}));
        System.out.println(firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1}));
    }
}
